// 二叉搜索树的第 k 个结点

// 给定一棵二叉搜索树，请找出其中的第 k 小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为 4。
// （5，3，7，2，4，6，8）结构如下
//      5
//    /   \
//   3     7
//  /  \  /  \
// 2   4  6   8

// 解题思路：
// 对二叉搜索树进行中序遍历,结果就是二叉搜索树的由小到大的顺序遍历
// 二叉搜索树的特性：左子树 < 根节点 < 右子树
// 故只需要找出二叉搜索树的中序，然后找第 k 个结点

// 对二叉搜索树进行中序遍历,结果就是二叉搜索树的由小到大的顺序遍历

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function KthNode(pRoot, k) {
  // write code here
  if (!pRoot || k < 1) {
    return null;
  }
  let res = [];
  function mid(root) {
    if (!root) return null;
    mid(root.left);
    res.push(root);
    mid(root.right);
  }
  mid(pRoot);
  return res[k - 1];
}
